package node;

import com.alibaba.fastjson.JSONObject;

public class NodeReverse {

    public static void main(String[] args) {
        Node head1 = new Node(1);
        Node node2 = new Node(4);
        Node node3 = new Node(7);
        Node node4 = new Node(9);


        Node head5 = new Node(2);
        Node node6 = new Node(5);
        Node node7 = new Node(8);
        Node node8 = new Node(10);
        Node node9 = new Node(11);

        head1.next = node2;
        node2.next = node3;
        node3.next = node4;

        head5.next = node6;
        node6.next = node7;
        node7.next = node8;
        node8.next = node9;


        //System.out.println(JSONObject.toJSONString(head1));
        Node newHead = merge(head1, head5);
        System.out.println(JSONObject.toJSONString(newHead));


    }

    public static Node merge(Node node1, Node node2){
        if(node1 == null && node2 == null){
            return null;
        }
        if(node1 == null){
            return node2;
        }
        if(node2 == null){
            return node1;
        }
        Node newHead = null;
        if(node1.getValue() > node2.getValue()){
            newHead = node2;
            newHead.next = merge(node1, node2.next);
        }else{
            newHead = node1;
            newHead.next = merge(node1.next, node2);
        }
        return newHead;
    }

    public static Node reverse(Node node){
        if(node == null || node.next == null){
            return node;
        }
        Node temp = node.next;
        Node newHead = reverse(node.next);
        temp.next = node;
        node.next = null;
        return  newHead;
    }

    public static Node reverse2(Node node){
        Node pre = null;
        Node next = null;
        while (node != null){
            next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }


    static class Node{

        private int value;

        private Node next;

        public Node(int value){
            this.value = value;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }
}
